package JZOffer;

import java.util.*;

/**
 * @author Lw中
 * @date 2021/8/28 21:57
 */
public class Jz52 {

    // Jz52.两个链表的第一个公共节点

    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
        val = x;
        next = null;
      }
  }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        // 方法一：使用哈希表进行存储其中一个链表的所有节点
//        Set<ListNode> set = new HashSet<>();
//        ListNode temp = headA;
//        // 循环存储节点
//        while (temp != null) {
//            set.add(temp);
//            temp = temp.next;
//        }
//        temp = headB;
//        // 遍历另一个链表寻找相同的节点
//        while (temp != null) {
//            if (set.contains(temp)) {
//                return temp;
//            }
//            temp = temp.next;
//        }
//        return null;

        // 方法二：使用双指针
        ListNode A = headA;
        ListNode B = headB;
        if (A == null || B == null) return null;
        while (A != B) {
            A = (A == null ? headB : A.next);
            B = (B == null ? headA : B.next);
        }
        return A;

    }

}
